One Hundred Prisoners and a Light Bulb by Hans van Ditmarsch & Barteld Kooi

Author:Hans van Ditmarsch & Barteld Kooi
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

10.2 How to Know Whom to Call

So far, we assumed that the friends can coordinate their actions before making any calls. In the Fixed Schedule protocol for four friends, first Amal calls Bharat, and then Chandra calls Devi, and so on. The way we defined the protocol was that any two friends can make the first call, and then any two other friends can make the second call. So it does not have to be between these exact four individuals. Can the protocol be rephrased such that these scheduling decisions can be made by the friends themselves, when they are about to call someone, and based on what they know? It turns out that this is not possible.

One can still imagine the first two callers be determined randomly. Everybody is dying to make a call, one of the friends is simply getting through before the others in making a call, the recipient of that call can be any other friend. We then assume that the information exchange takes place instantly without consuming time and we can schedule the next call. All friends only know their own secret initially.

But for the second call we now have a problem. After the first call there are two friends who know two secrets, and the remaining friends only know one secret. In other words, they have different knowledge. In order to attempt to copy the Fixed Schedule protocol, we may pick any friend who only knows one secret to initiate the second call; this choice is knowledge-based (and anyone fulfilling the condition can be chosen), and this rules out those who made the first call. This friend now has to call another friend who only knows one secret. But the friend initiating that second call cannot choose such a one-secret-only friend based on his knowledge. If Chandra initiates the second call, and if she is ignorant about who made the first call, then she has no reason to prefer Devi over any other friend. It seems not unreasonable to assume that she only knows that she was not involved herself in that first call. This means that, from Chandra’s point of view, the first call could have been between Amal and Bharat, or between Amal and Devi, or between Bharat and Devi. She does not know which call really happened! A second call between Chandra and Devi has to be “fixed” by an external scheduler (or by the friends themselves, prior to executing the protocol); it cannot be chosen by the friends themselves based on what they learn from receiving calls.

We conclude that it is not possible for the friends themselves to enforce the execution of the Fixed Schedule protocol.

Let us now consider an epistemic protocol wherein a friend calls another friend depending on its knowledge only, and such that any friend fulfilling the knowledge condition is chosen at random.

Protocol 10 (Learn New Secrets) Until all friends know all secrets: choose a friend who does not know all secrets, let this friend choose a friend whose secret he does not know, and make that call.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.